package com.example.searching_and_sorting;

import java.util.ArrayList;
import java.util.List;

public class Searching {
    //  线性查找
    public static String linearSearch(int[] data,int target)
    {
        int index = 0;
        String result = "线性查找 : ";
        while (index < data.length)
        {
            if (data[index]==target){
                result += String.valueOf(data[index]);
                break;
            }
            else {
                index++;
                if (index>=data.length){
                    result+= null;
                }
            }
        }
        return result;
    }


    //  二分查找
    public static String BinarySearch_non_recursion(int[] data,int target){
        int min,max,midpoint;
        min = 0;max = data.length-1;
        String result = "二分查找 : ";
        while (min<=max){
            midpoint = (min + max) / 2;
            if (data[midpoint]==target){
                result += String.valueOf(data[midpoint]);
                break;
            }
            if (data[midpoint]>target){
                max = midpoint - 1;
            }
            if (data[midpoint]<target){
                min = midpoint + 1;
            }
        }
        return result;
    }
    public static String BinarySearch_recursion(int[] data,int min,int max,int target){

        int midpoint = (max + min) / 2;
        String result = "二分查找 ：";
        while (min>max){
            result+=null;
            return result;
        }
        if (data[midpoint]==target){
            result += data[midpoint];
            return result;
        }
        if (data[midpoint]>target){
            return BinarySearch_recursion(data,min,midpoint-1,target);
        }
        if (data[midpoint]<target){
            return BinarySearch_recursion(data,midpoint+1,max,target);
        }

        return result;
    }

    //  插值查找
    public static String InsertionSearch(int[] data,int min, int max,int target) {
        String result = "插值查找 ： ";
        while (max<=min){
            result +=null;
            return result;
        }
        int midpoint = min + (target - data[min]) / (data[max] - data[min]) * (max - min);


        if (data[midpoint] == target) {
            result += String.valueOf(data[midpoint]);
            return result;
        }
        else
            if (data[midpoint] > target) {
                return InsertionSearch(data, min, midpoint - 1, target);
            }
            else {
                return InsertionSearch(data, midpoint + 1, max, target);
            }
    }
    //  斐波那契查找
    public static class FibonacciSearch{
        public final static int max_size = 20;
        public static int[] Fibonacci(){
            int[] F = new int[max_size];
            F[0] = 0;
            F[1] = 1;
            for(int i=2;i<max_size;++i) {
                F[i]=F[i-1]+F[i-2];
            }
            return F;
        }
        public static String FibonacciSearch(int []data,int target){
            int min = 0;
            int max = data.length-1;
            int mid = 0;
            String result = "斐波那契查找 ：";
            int k = 0;   // 斐波那契分割数值下标
            int i = 0;   // 序列元素个数
            int[] F = Fibonacci();    // 获取斐波那契数列
            // 获取斐波那契分割数值下标
            while (data.length > F[k] - 1) {
                ++k;
            }
            // 创建临时数组
            int[] temp = new int[F[k] - 1];
            for (int j = 0; j < data.length;j++){
                temp[j] = data[j];
            }
            for (int j : temp) {
                System.out.print(j + " ");
            }
            System.out.println();
            while (min <= max) {
                // min：起始位置
                // 前半部分有f[k-1]个元素，由于下标从0开始
                // 则-1 获取 黄金分割位置元素的下标
                mid = min + F[k - 1] - 1;

                if (temp[mid] > target) {
                    // 查找前半部分，高位指针移动
                    max = mid - 1;
                    // （全部元素） = （前半部分）+（后半部分）
                    // f[k] = f[k-1] + f[k-1]
                    // 因为前半部分有f[k-1]个元素，所以 k = k-1
                    k = k - 1;
                } else if (temp[mid] < target) {
                    // 查找后半部分，高位指针移动
                    min = mid + 1;
                    // （全部元素） = （前半部分）+（后半部分）
                    // f[k] = f[k-1] + f[k-1]
                    // 因为后半部分有f[k-1]个元素，所以 k = k-2
                    k = k - 2;
                } else {
                    // 如果为真则找到相应的位置
                    if (mid <= max) {
                        result += String.valueOf(data[mid]);
                        return result;
                    } else {
                        // 出现这种情况是查找到补充的元素
                        // 而补充的元素与max位置的元素一样
                        result += String.valueOf(data[max]);
                        return result;
                    }
                }
            }
            result +=null;
            return result;
    }

    }

    // 树表查找
    public static String Tree_table_lookup(int[] data,int target){
       LinkedBinarySearchTree linkedBinarySearchTree = new LinkedBinarySearchTree();
        String result = "树表查找 ： ";
        for (int d : data){
            linkedBinarySearchTree.addElement(d);
        }
        result +=  String.valueOf(linkedBinarySearchTree.find(target));
        return result;
    }

    // 分块查找
    public static class BlockSearch {
        public static int[] index;
        public static ArrayList[] list;
        /**
         * 初始化索引表
         * @param index
         */
        public BlockSearch(int[] index) {
            if (index != null && index.length != 0) {
                BlockSearch.index = index;
                list = new ArrayList[index.length];
                for (int i = 0; i < list.length; i++) {
                    list[i] = new ArrayList();
                }
            } else {
                throw new Error("index cannot be null or empty.");
            }
        }
        /**
         * 插入元素
         * @param value
         */
        public static void insert(int value) {
            int i = binarySearch(value);
            list[i].add(value);
        }

        /**
         * 查找元素
         * @param data
         * @return
         */
        public static String search(int data) {
            int i = binarySearch(data);
            String result = null;
            for (int j = 0; j < list[i].size(); j++) {
                if ((int)list[i].get(j) == data) {
                    result = String.valueOf(list[i].get(j));
                    return result;
                }
            }
            return result;
        }
        /**
         * 打印每块元素
         */
        public static void printAll() {
            for (int i = 1; i < list.length; i++) {
                ArrayList l = list[i];
                System.out.print("第" + i + "块:");
                for (int j = 0; j < l.size(); j++) {
                    System.out.print(l.get(j) + " ");
                }
                System.out.println();
            }
        }
        /**
         * 二分查找定位索引位置
         * @param data 要插入的值
         * @return
         */
        private static int binarySearch(int data) {
            int start = 0;
            int end = index.length-1;
            int mid = 0;
            while (start <= end) {
                mid = (start + end) / 2;
              if (data<=index[mid]) {
                  end = mid - 1;
              }
              else {
                  start = mid + 1;
              }
            }
            return start;
        }
    }
    //  哈希查找
    public static void main(String[] args) {

        int n = 100;
        int [] a = new int[] {1,3,6,9,12,11,2319,4};

        System.out.println(Searching.linearSearch(a,3));

    }
    /**

     * 得到1到n之间的素数，存到一个ArrayList集合

     */

    public static List<Integer> getPrimeNumberToN(int n) {

        List<Integer> result = new ArrayList<>();

        for (int i = 1; i < n + 1; i++) {

            if (numberIsPrime(i)) {

                result.add(i);

            }

        }
        return result;
    }
    /**

     * 判断一个数是不是素数：只能被1和本身整除

     * <p>

     * 说明：从2开始除，不需要到n，也就是循环条件是 < n 就可以，这之间只要被整除了，那么他就不是素数了

     */
    private static boolean numberIsPrime(int n) {

        for (int i = 2; i < n; i++) {

            if (n % i == 0) {

                return false;

            }
        }
        return true;
    }
    public static String HashSearching(int[] data,int k,int target){
        int position = target % k;
        String result = "哈希查找 ：";
        int di =1;
        while (data[position]!=0&&data[position]!=target){
            position = (position+di)%k;
            if (k-1<=di){
                break;
            }
        }
        if (data[position]==0||data[position]!=target){
            result += null;
        }
        else if(data[position]!=0&&data[position]==target) {
            result += String.valueOf(data[position]);
        }
        return result;
    }
    public static void Hashinsert(int[] data,int k,int target){
        int position = target % k;
        int di =1;
        while (data[position]!=0){
            position = (position+di)%k;
            di++;
            if (k-1<=di){
                break;
            }
        }
        data[position] = target;
    }

}
